/*
* AVLTree.h
*
*  Created on: Apr 10, 2011
*      Author: boris
*/

#ifndef AVLTREE_H_
#define AVLTREE_H_

#include <iostream>

using std::cerr;
using std::endl;

#include "mypair.h"
#include "myvector.h"
#include "rational.h"

using namespace rational;

class KeyAlreadyInTreeException : public std::exception {};
class KeyNotInTreeException : public std::exception {};
class IndexOutOfRangeException : public std::exception {};
class VectorNotSortedException : public std::exception {};
class InvalidLatitudeRangeException : public std::exception {};
class EmptyLatitudeRangeException : public std::exception {};


/**
 * This class represents a self-balancing binary search tree
 * which can contain data in form of key-value.
 * Uses the AVL algorithm.
 */
template <class TKEY, class TVAL, class TTEMPGEN, class TLATGEN>
		class AVLTree
{
public:
	/**
	 * Empty C'tor
	 * \return Empty AVL Tree
	 * \remarks Complexity of O(1)
	 */
	AVLTree(void) :
			_root(NULL), _numberOfNodes(0)
	{
	}

	/**
	 * D'tor
	 * Deletes AVL Tree
	 * \remarks Complexity of O(n)
	 */
	~AVLTree(void)
	{
		delete _root;
	}

	/**
	 * Copy C'tor
	 * \return new AVL Tree, identical to parameter
	 * \remarks Complexity of O(n)
	 */
	AVLTree(const AVLTree& other) :
			_root(CloneTree(other._root)),
			_numberOfNodes(other._numberOfNodes)
	{
	}

	/**
	 * Assignment operator - modifies current tree to be identical to other
	 * \return AVL Tree, identical to parameter
	 * \remarks Complexity of O(n+m), where n is the number of nodes in
	 * \remarks	  current tree and m is the number of nodes in the other tree
	 */
	AVLTree& operator = (const AVLTree& other)
	{
		if (&other==this)
		{
			return *this;
		}
		delete _root;
		_root = CloneTree(other._root);
		_numberOfNodes = other._numberOfNodes;
	}

private:
	struct TreeNode
	{
	public:
		/**
		 * C'tor
		 * \return new Tree node
		 * \remarks Complexity of O(1)
		 */
		TreeNode(const TKEY& k, const TVAL& v,
				 const TTEMPGEN& tempGen) :
				key(k), value(v), balance(0), height(1), countSubTree(1),
				sumTempSubTree(tempGen(v)), maxTempSubTree(tempGen(v)),
				left(NULL), right(NULL)
		{
		}

		/**
		 * D'tor
		 * Deletes tree node and all its subtree
		 * \remarks Complexity of O(n)
		 */
		~TreeNode()
		{
			delete left;
			delete right;
		}
	public:
		TKEY key;
		TVAL value;
		int balance;
		int height;
		int countSubTree;
		Rational sumTempSubTree;
		Rational maxTempSubTree;
		TreeNode* left;
		TreeNode* right;
	};

	TreeNode* _root;
	int _numberOfNodes;
	TTEMPGEN _tempGen;
	TLATGEN  _latitudeGen;

private:
	/**
	 * Creates and returns a copy of a tree node
	 * (deep copy - include all subtree)
	 * \return tree node
	 * \remarks Complexity of O(n)
	 */
	TreeNode* CloneTree(const TreeNode* node) const
	{
		if (node==NULL)
		{
			return NULL;
		}
		TreeNode* res = new TreeNode(node->key, node->value);
		res->balance = node->balance;
		res->height = node->height;
		res->countSubTree = node->countSubTree;
		res->maxTempSubTree = node->maxTempSubTree;
		res->sumTempSubTree = node->sumTempSubTree;
		res->left = CloneTree(node->left);
		res->right = CloneTree(node->right);
		return res;
	}

	/**
	 * returns the maximus of two objects with > operator
	 * \return B
	 * \remarks Complexity of O(1)
	 */
	template <class B>
	B max(B x, B y) const
	{
		if (x>y)
		{
			return x;
		}
		else
		{
			return y;
		}
	}

	/**
	 * Finds a key in the tree
	 * \return tree node with required key or NULL
	 * \remarks Complexity of O(log n)
	 */
	const TreeNode* FindKey(const TreeNode* node, const TKEY& key) const
	{
		if (node==NULL)
		{
			return NULL;
		}
		if (node->key == key)
		{
			return node;
		}
		else if (key > node->key)
		{
			return FindKey(node->right, key);
		}
		else
		{
			return FindKey(node->left, key);
		}
	}

	/**
	 * Gets the height of tree node
	 * if tree node is NULL, returns zero
	 * height is retrieved from tree node's field, not calculated.
	 * \return height of tree node
	 * \remarks Complexity of O(1)
	 */
	int GetHeight(const TreeNode* node) const
	{
		if (node==NULL)
		{
			return 0;
		}
		else
		{
			return node->height;
		}
	}

	/**
	 * Recalculates and returns the height of tree node
	 * if tree node is NULL, does not claculate height and returns zero
	 * height of left & right subtrees is retrieved from tree node's
	 * field, not calculated.
	 * \return height of tree node
	 * \remarks Complexity of O(1)
	 */
	int CalculateHeight(TreeNode* node)
	{
		if (node!=NULL)
		{
			return node->height = 1 + max(GetHeight(node->left), GetHeight(node->right));
		}
		else
		{
			return 0;
		}
	}

	/**
	 * Recalculates the balance factor of tree node
	 * \return none
	 * \remarks Complexity of O(1)
	 */
	void CalculateBalanceFactor(TreeNode* node)
	{
		CalculateHeight(node);
		node->balance = CalculateHeight(node->right) - CalculateHeight(node->left);
	}

	/**
	 * Calculates the ranking data, for any given node, we calculate all the
	 * relevant data in its subtree.
	 * all data is retrieved from the immediate decendenants which are O(1) time comlexity
	 * \return none
	 * \remarks Complexity of O(1)
	 */
	void CalculateRankingData(TreeNode* node)
	{
		if (node==NULL)
		{
			return;
		}

		node->countSubTree = 1;
		node->maxTempSubTree = node->sumTempSubTree =  _tempGen(node->value);
		if (node->right)
		{
			node->countSubTree += node->right->countSubTree;
			node->sumTempSubTree += node->right->sumTempSubTree;
			node->maxTempSubTree = max(node->maxTempSubTree, node->right->maxTempSubTree);
		}
		if (node->left)
		{
			node->countSubTree += node->left->countSubTree;
			node->sumTempSubTree += node->left->sumTempSubTree;
			node->maxTempSubTree = max(node->maxTempSubTree, node->left->maxTempSubTree);
		}
	}

	/**
	 * Performs Left-Left rotation in accordance with the AVL algorithm
	 * \return new relative root
	 * \remarks Complexity of O(1)
	 */
	TreeNode* RotateLeftLeft(TreeNode* currNode)
	{
		TreeNode* left = currNode->left;
		TreeNode* afterLeft = left->right;

		currNode->left = afterLeft;
		CalculateBalanceFactor(currNode);

		left->right = currNode;
		CalculateBalanceFactor(left);

		CalculateRankingData(currNode);
		CalculateRankingData(left);

		return left;
	}

	/**
	 * Performs Right-Right rotation in accordance with the AVL algorithm
	 * \return new relative root
	 * \remarks Complexity of O(1)
	 */
	TreeNode* RotateRightRight(TreeNode* currNode)
	{
		TreeNode* right = currNode->right;
		TreeNode* beforeRight = right->left;

		currNode->right = beforeRight;
		CalculateBalanceFactor(currNode);

		right->left = currNode;
		CalculateBalanceFactor(right);

		CalculateRankingData(currNode);
		CalculateRankingData(right);
		return right;
	}

	/**
	 * Performs Left-Right rotation in accordance with the AVL algorithm
	 * \return new relative root
	 * \remarks Complexity of O(1)
	 */
	TreeNode* RotateLeftRight(TreeNode* currNode)
	{
		TreeNode* left = currNode->left;
		TreeNode* afterLeft = left->right;

		left->right = afterLeft->left;
		CalculateBalanceFactor(left);

		currNode->left = afterLeft->right;
		CalculateBalanceFactor(currNode);

		afterLeft->right = currNode;
		afterLeft->left = left;
		CalculateBalanceFactor(afterLeft);

		CalculateRankingData(currNode);
		CalculateRankingData(left);
		CalculateRankingData(afterLeft);

		return afterLeft;
	}

	/**
	 * Performs Right-Left rotation in accordance with the AVL algorithm
	 * \return new relative root
	 * \remarks Complexity of O(1)
	 */
	TreeNode* RotateRightLeft(TreeNode* currNode)
	{
		TreeNode* right = currNode->right;
		TreeNode* beforeRight = right->left;

		right->left = beforeRight->right;
		CalculateBalanceFactor(right);

		currNode->right = beforeRight->left;
		CalculateBalanceFactor(currNode);

		beforeRight->left = currNode;
		beforeRight->right = right;
		CalculateBalanceFactor(beforeRight);

		CalculateRankingData(currNode);
		CalculateRankingData(right);
		CalculateRankingData(beforeRight);

		return beforeRight;
	}

	/**
	 * Checks balance factor, and performs rotation is needed
	 * \return new relative root
	 * \remarks Complexity of O(1)
	 */
	TreeNode* RebalanceTree(TreeNode* currNode)
	{
		if (currNode->balance == 2 && currNode->right->balance >= 0)
		{
			return RotateRightRight(currNode);
		}
		else if (currNode->balance == 2 && currNode->right->balance <= -1)
		{
			return RotateRightLeft(currNode);
		}
		else if (currNode->balance == -2 && currNode->left->balance >= 1)
		{
			return RotateLeftRight(currNode);
		}
		else if (currNode->balance == -2 && currNode->left->balance <= 0)
		{
			return RotateLeftLeft(currNode);
		}
		return currNode;
	}

	/**
	 * Inserts a new item into the subtree of current tree node
	 * if current node is NULL, creates a new tree node and returns it.
	 * \return new relative root
	 * \remarks Complexity of O(log n)
	 */
	TreeNode* InsertKey(TreeNode* node, const TKEY& key, const TVAL& value)
	{
		if (node==NULL)
		{
			TreeNode* res = new TreeNode(key, value, _tempGen);
			return res;
		}
		TreeNode* res;
		if (node->key == key)
		{
			throw KeyAlreadyInTreeException();
		}
		else if (key > node->key)
		{
			res = InsertKey(node->right, key, value);
			node->right = res;
		}
		else
		{
			res = InsertKey(node->left, key, value);
			node->left = res;
		}
		CalculateBalanceFactor(node);
		CalculateRankingData(node);
		return RebalanceTree(node);
	}

	/**
	 * Deletes current node
	 * Assumes current node is a leaf
	 * \return parent (if exists) or NULL
	 * \remarks Complexity of O(1)
	 */
	TreeNode* DeleteLeaf(TreeNode* currNode, TreeNode* lParent, TreeNode* rParent)
	{
		delete currNode;
		if (lParent != NULL)
		{
			lParent->left = NULL;
			CalculateBalanceFactor(lParent);
			CalculateRankingData(lParent);
			return lParent;
		}
		else if (rParent != NULL)
		{
			rParent->right = NULL;
			CalculateBalanceFactor(rParent);
			CalculateRankingData(rParent);
			return rParent;
		}
		else
		{
			return NULL;
		}
	}

	/**
	 * Deletes current node
	 * Assumes current node has only a right branch
	 * \return new relative root
	 * \remarks Complexity of O(1)
	 */
	TreeNode* DeleteNodeWithRightBrach(TreeNode* currNode, TreeNode* lParent, TreeNode* rParent)
	{
		TreeNode* next = currNode->right;
		currNode->right = NULL;
		delete currNode;
		if (lParent != NULL)
		{
			lParent->left = next;
			CalculateBalanceFactor(lParent);
			CalculateRankingData(next);
			CalculateRankingData(lParent);
		}
		else if (rParent != NULL)
		{
			rParent->right = next;
			CalculateBalanceFactor(rParent);
			CalculateRankingData(next);
			CalculateRankingData(rParent);
		}
		return next;
	}

	/**
	 * Deletes current node
	 * Assumes current node has only a left branch
	 * \return new relative root
	 * \remarks Complexity of O(1)
	 */
	TreeNode* DeleteNodeWithLeftBrach(TreeNode* currNode, TreeNode* lParent, TreeNode* rParent)
	{
		TreeNode* prev = currNode->left;
		currNode->left = NULL;
		delete currNode;
		if (lParent != NULL)
		{
			lParent->left = prev;
			CalculateBalanceFactor(lParent);
			CalculateRankingData(prev);
			CalculateRankingData(lParent);
		}
		else if (rParent != NULL)
		{
			rParent->right = prev;
			CalculateBalanceFactor(rParent);
			CalculateRankingData(prev);
			CalculateRankingData(rParent);
		}
		return prev;
	}

	template <class S>
	void Swap(S& x, S& y)
	{
		S tmp = x;
		x = y;
		y= tmp;
	}

	/**
	 * Deletes current node
	 * Assumes current node has both branch
	 * \return new relative root
	 * \remarks Complexity of O(log n)
	 */
	TreeNode* DeleteNodeWithBothBraches(TreeNode* currNode)
	{
		TreeNode* next = currNode->right;
		while (next!=NULL && next->left!=NULL)
		{
			next = next->left;
		}
		Swap(currNode->key,next->key);
		Swap(currNode->value,next->value);
		TreeNode* newRight = DeleteKey(currNode->right, NULL, currNode, next->key);
		CalculateRankingData(newRight);
		if (newRight!=NULL && (newRight->right == currNode || newRight->left == currNode))
		{
			return newRight;
		}
		if (newRight!=currNode)
		{
			currNode->right = newRight;
		}
		else
		{
			currNode->right = NULL;
		}
		CalculateRankingData(currNode);
		return currNode;
	}

	/**
	 * Finds and deletes key from subtree of current tree node
	 * \return new relative root
	 * \remarks Complexity of O(log n)
	 */
	TreeNode* DeleteKey(TreeNode* currNode, TreeNode* lParent, TreeNode* rParent, const TKEY& key)
	{
		if (currNode==NULL)
		{
			throw KeyNotInTreeException();
		}

		if (currNode->key == key)
		{
			TreeNode* res;
			if (currNode->left == NULL && currNode->right == NULL)
			{
				res = DeleteLeaf(currNode, lParent, rParent);
			}
			else if (currNode->left == NULL)
			{
				res = DeleteNodeWithRightBrach(currNode, lParent, rParent);
			}
			else if (currNode->right == NULL)
			{
				res = DeleteNodeWithLeftBrach(currNode, lParent, rParent);
			}
			else
			{
				res = DeleteNodeWithBothBraches(currNode);
			}
			if (res!=NULL)
			{
				CalculateBalanceFactor(res);
				CalculateRankingData(res);
				return RebalanceTree(res);
			}
			else
			{
				return NULL;
			}
		}
		else if (key > currNode->key)
		{
			TreeNode* newRight = DeleteKey(currNode->right, NULL, currNode, key);
			if (newRight!=NULL && (newRight->right == currNode || newRight->left == currNode))
			{
				currNode = newRight;
			}
			else if (currNode != newRight)
			{
				currNode->right = newRight;
			}
		}
		else
		{
			TreeNode* newLeft = DeleteKey(currNode->left, currNode, NULL, key);
			if (newLeft!=NULL && (newLeft->right == currNode || newLeft->left == currNode))
			{
				currNode = newLeft;
			}
			else if (currNode != newLeft)
			{
				currNode->left = newLeft;
			}
		}
		CalculateBalanceFactor(currNode);
		CalculateRankingData(currNode);
		return RebalanceTree(currNode);
	}

	/**
	 * Update a value in the tree by key
	 * \return true if update was successful, false otherwise
	 * \remarks Complexity of O(log n)
	 */
	bool UpdateValue(TreeNode* node, const TKEY& key, const TVAL& value)
	{
		if (node==NULL)
		{
			return false;
		}
		bool res;
		if (node->key == key)
		{
			node->value = value;
			CalculateRankingData(node);
			res = true;
		}
		else if (key > node->key)
		{
			res = UpdateValue(node->right, key, value);
			CalculateRankingData(node);
		}
		else
		{
			res = UpdateValue(node->left, key, value);
			CalculateRankingData(node);
		}
		return res;
	}

	/**
	 * Writes keys and values of current tree node's subtree into a vector
	 * Tree is searched in-order
	 * \return none
	 * \remarks Complexity of O(n)
	 */
	void FlattenTree(const TreeNode* currNode, myVector<myPair<TKEY,TVAL> >& res) const
	{
		if (currNode==NULL)
		{
			return;
		}
		FlattenTree(currNode->left, res);
		res.push_back(myPair<TKEY,TVAL>(currNode->key, currNode->value));
		FlattenTree(currNode->right, res);
	}

	/**
	 * Builds a balanced sorted binary search tree from vector
	 * Only items from begin to end are used (including begin, excluding end)
	 * \return root of new tree
	 * \remarks Complexity of O(n)
	 */
	TreeNode* BuildTreeFromVector(const myVector<myPair<TKEY,TVAL> >& vec,
								  int begin, int end)
	{
		if (begin==end)
		{
			return NULL;
		}

		int middle = (begin + end) / 2;
		TreeNode* currNode = new TreeNode(vec[middle].first, vec[middle].second);
		currNode->left = BuildTreeFromVector(vec, begin, middle);
		currNode->right = BuildTreeFromVector(vec, middle+1, end);
		CalculateHeight(currNode);
		CalculateBalanceFactor(currNode);
		CalculateRankingData(currNode);
		return currNode;
	}

	/**
	 * for any two given latitudes we find the top most node that has a latitude
	 * between fromLatitude,toLatitude inclusive non-greedy
	 * \return the top most node that is valid
	 * \remarks Complexity of O(log n)
	 */
	const TreeNode* FindTopmostNodeInRange(const TreeNode* currNode, Rational fromLatitude, Rational toLatitude) const
	{
		if (currNode==NULL)
		{
			return NULL;
		}
		const TreeNode* findRes;
		if (_latitudeGen(currNode->key) > toLatitude)
		{
			findRes = FindTopmostNodeInRange(currNode->left, fromLatitude, toLatitude);
		}
		else if (_latitudeGen(currNode->key) < fromLatitude)
		{
			findRes = FindTopmostNodeInRange(currNode->right, fromLatitude, toLatitude);
		}
		else // between from and to, inclsive
		{
			findRes = currNode;
		}

		return findRes;

	}


	/**
	 * This finds the maximal temperature in a given subtree, if findLeft then only nodes
	 *  with latitude greater than or equal to latitudeLimit will be searched, otherwise, nodes
	 *  with latitude less than or equal to latitudeLimit.
	 * \param a pointer to the subtree
	 * \param the latitude limit with correspondence to findLeft
	 * \param a boolean for knowing which values should we select
	 * \param where the result will be stored
	 * \return a boolean value which states if the search yielded any valid results
	 * \remarks Complexity of O(log n)
	 */
	bool FindMaxTempInHalfRange(const TreeNode* currNode, Rational latitudeLimit, bool findLeft, Rational& res) const
	{
		if (currNode==NULL)
		{
			return false;
		}
		Rational currLatitude = _latitudeGen(currNode->key);
		if (findLeft)
		{
			if (currLatitude >= latitudeLimit)
			{
				Rational maxTemp = _tempGen(currNode->value);
				if (currNode->right)
				{
					maxTemp = max(maxTemp, currNode->right->maxTempSubTree);
				}
				Rational maxLeft;
				if (FindMaxTempInHalfRange(currNode->left, latitudeLimit, findLeft, maxLeft))
				{
					maxTemp = max(maxTemp, maxLeft);
				}
				res = maxTemp;
				return true;
			}
			else
			{
				return FindMaxTempInHalfRange(currNode->right, latitudeLimit, findLeft, res);
			}
		}
		else
		{
			if (currLatitude <= latitudeLimit)
			{
				Rational maxTemp = _tempGen(currNode->value);
				if (currNode->left)
				{
					maxTemp = max(maxTemp, currNode->left->maxTempSubTree);
				}
				Rational maxRight;
				if (FindMaxTempInHalfRange(currNode->right, latitudeLimit, findLeft, maxRight))
				{
					maxTemp = max(maxTemp, maxRight);
				}
				res = maxTemp;
				return true;
			}
			else
			{
				return FindMaxTempInHalfRange(currNode->left, latitudeLimit, findLeft, res);
			}
		}
	}

	/**
	 * This finds the finds and counts the temperatures of nodes with latitude up to the parameter latitude
	 * \param a pointer to the subtree
	 * \param the latitude limit with correspondence to findLeft
	 * \param a boolean for knowing which values should we select
	 * \param where the result sum will be stored
	 * \param where the result count will be stored
	 * \remarks Complexity of O(log n)
	 */
	void SumAndCountByLatitude(const TreeNode* currNode, Rational latitude, bool findLeft, Rational& sumTemp, int& countNodes) const
	{
		if (currNode==NULL)
		{
			sumTemp = 0;
			countNodes = 0;
			return;
		}

		Rational currLatitude = _latitudeGen(currNode->key);

		if (currLatitude > latitude)
		{
			SumAndCountByLatitude(currNode->left, latitude, findLeft, sumTemp, countNodes);
		}
		else if (currLatitude < latitude)
		{
			SumAndCountByLatitude(currNode->right, latitude, findLeft, sumTemp, countNodes);
		}
		else if (currLatitude == latitude)
		{
			if (findLeft)
			{
				SumAndCountByLatitude(currNode->left, latitude, findLeft, sumTemp, countNodes);
			}
			else
			{
				SumAndCountByLatitude(currNode->right, latitude, findLeft, sumTemp, countNodes);
			}
		}

		if (currLatitude < latitude || (currLatitude == latitude && !findLeft))
		{
			sumTemp += _tempGen(currNode->value);
			countNodes += 1;
			if (currNode->left)
			{
				sumTemp += currNode->left->sumTempSubTree;
				countNodes += currNode->left->countSubTree;
			}
		}
	}

public:
	/**
	 * Inserts a new item into tree
	 * \return none
	 * \remarks Complexity of O(log n)
	 */
	void InsertKey(const TKEY& key, const TVAL& value)
	{
		_root  = InsertKey(_root, key, value);
		_numberOfNodes += 1;
	}

	/**
	 * Finds an item with given key in tree
	 * \return value of given tree
	 * \remarks Complexity of O(log n)
	 */
	TVAL FindKey(const TKEY& key) const
	{
		const TreeNode* res = FindKey(_root, key);
		if (res==NULL)
		{
			throw KeyNotInTreeException();
		}
		else
		{
			return res->value;
		}
	}

	/**
	 * Deletes item with given key from tree
	 * \return none
	 * \remarks Complexity of O(log n)
	 */
	void DeleteKey(const TKEY& key)
	{
		TreeNode* res = DeleteKey(_root, NULL, NULL, key);
		_root = res;
		_numberOfNodes -= 1;
	}

	/**
	 * Update a value in the tree by key
	 * \return true if update was successful, false otherwise
	 * \remarks Complexity of O(log n)
	 */
	bool UpdateValue(const TKEY& key, const TVAL& value)
	{
		return UpdateValue(_root, key, value);
	}

	/**
	 * Returns the number of items in tree
	 * \return number of items
	 * \remarks Complexity of O(1)
	 */
	int Size() const
	{
		return _numberOfNodes;
	}

	/**
	 * this gets the average temperature between the two given latitudes
	 * \return the average of the temperatures
	 * \remarks Complexity O(log n)
	 */
	Rational GetAvgTemperatureByRange(Rational minLatitude, Rational maxLatitude) const
	{
		if (minLatitude > maxLatitude) {
			throw InvalidLatitudeRangeException();
		}
		Rational sumTemperatureToMin, sumTemperatureToMax;
		int countToMin, countToMax;
		SumAndCountByLatitude(_root, minLatitude, true, sumTemperatureToMin, countToMin);
		SumAndCountByLatitude(_root, maxLatitude, false, sumTemperatureToMax, countToMax);

		if (countToMax <= countToMin)
		{
			throw EmptyLatitudeRangeException();
		}
		return (sumTemperatureToMax - sumTemperatureToMin)/Rational(countToMax - countToMin);
	}

	/**
	 * this finds the maxmial temperature between the two given latitudes
	 * \return the maximal value
	 * \remarks Complexity of O(log n)
	 */
	Rational FindMaxTempInRange(Rational fromLatitude, Rational toLatitude) const
	{
		if (fromLatitude > toLatitude) {
			throw InvalidLatitudeRangeException();
		}
		const TreeNode* topmostInRange = FindTopmostNodeInRange(_root, fromLatitude, toLatitude);
		if (topmostInRange)
		{
			Rational maxTemp = _tempGen(topmostInRange->value);
			Rational maxLeft, maxRight;
			if (FindMaxTempInHalfRange(topmostInRange->left, fromLatitude, true, maxLeft))
			{
				maxTemp = max(maxTemp, maxLeft);
			}
			if (FindMaxTempInHalfRange(topmostInRange->right, toLatitude, false, maxRight))
			{
				maxTemp = max(maxTemp, maxRight);
			}
			return maxTemp;
		}
		else
		{
			throw EmptyLatitudeRangeException();
		}
	}

	/**
	 * Writes keys and values of current tree node's subtree into a vector
	 * Tree is searched in-order
	 * vector is emptied before writing values
	 * \return none
	 * \remarks Complexity of O(n)
	 */
	void FlattenTree(myVector<myPair<TKEY, TVAL> >& res) const
	{
		res.clear();
		res.reserve(_numberOfNodes);
		FlattenTree(_root, res);
	}

	/**
	 * Builds a balanced sorted binary search tree from vector
	 * current tree is entirely replaced
	 * \return none
	 * \remarks Complexity of O(n)
	 */
	void BuildTreeFromVector(const myVector<myPair<TKEY, TVAL> > &vec)
	{
		int vecSize = vec.Size();
		for (int i=0; i<vecSize-1; ++i)
		{
			if (!(vec[i+1].first > vec[i].first))
			{
				throw VectorNotSortedException();
			}
		}
		delete _root;
		_numberOfNodes = vecSize;
		_root = BuildTreeFromVector(vec,0,vecSize);
	}

	/**
	 * Deletes all items in tree
	 * \return none
	 * \remarks Complexity of O(n)
	 */
	void Clear()
	{
		delete _root;
		_root = NULL;
		_numberOfNodes = 0;
	}

	myPair<TKEY, TVAL> Max() const
	{
		if (_root!=NULL)
		{
			TreeNode* currNode = _root;
			while (currNode->right != NULL)
			{
				currNode = currNode->right;
			}
			return myPair<TKEY, TVAL> (currNode->key, currNode->value);
		}
		else
		{
			throw IndexOutOfRangeException();
		}
	}


};

#endif /* AVLTREE_H_ */
